package jm.algorithm.graph;

import com.sun.org.apache.regexp.internal.RE;

import java.util.*;

/**
 * @Description 邻接表 实现图
 * @date 2022/5/10 20:38
 */
@SuppressWarnings("unchecked")
public class ListGraph<V,E> extends Graph<V,E>{

    // 存放顶点及它对应的顶点信息
    private Map<V, Vertex<V, E>> vertices = new HashMap<>();


    // 比较器
    private Comparator<Edge<V, E>> edgeComparator = (Edge<V, E> e1, Edge<V, E> e2) -> {
        return weightManager.compare(e1.weight, e2.weight);
    };

    // 存放边信息
    private Set<Edge<V, E>> edges = new HashSet<>();

    public ListGraph() {}

    public ListGraph(WeightManager<E> weightManager) {
        super(weightManager);
    }
    @Override
    public int edgeSize() {
        return edges.size();
    }

    @Override
    public int verticesSize() {
        return vertices.size();
    }

    @Override
    public void addVertex(V v) {
        if (vertices.containsKey(v)) return;
        vertices.put(v,new Vertex<>(v));
    }

    @Override
    public void addEdge(V from, V to) {
        addEdge(from, to ,null);
    }

    @Override
    public void addEdge(V from, V to, E weight) {
        // 判断当前顶点是否存在
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null){
            fromVertex = new Vertex<>(from);
            vertices.put(from,fromVertex);
        }

        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null){
            toVertex = new Vertex<>(to);
            vertices.put(to,toVertex);
        }

        // 新建一个边
        Edge<V, E> edge = new Edge<>(fromVertex, toVertex, weight);

        // 删除原有的边（没有就删除不了）
        if (fromVertex.outEdges.remove(edge)) {
            toVertex.inEdges.remove(edge);
            edges.remove(edge);
        }

        // 新建两个顶点之间的边

        // 当前边是
        //  1. 起点fromVertex 的出度
        //  2. 终点toVertex 的入度
        fromVertex.outEdges.add(edge);
        toVertex.inEdges.add(edge);
        edges.add(edge);
    }

    @Override
    public void removeVertex(V v) {
        // 直接从 map 中删除如果为空就表示不存在不需要再进行操作。
        Vertex<V, E> vertex = vertices.remove(v);
        if (vertex == null) return;

        // 删除当前顶点时 还需要删除当前顶点作为 起点 和 终点 的边。

        // 当前节点的作为出度的迭代器
        Iterator<Edge<V, E>> outIterator = vertex.outEdges.iterator();
        while (outIterator.hasNext()) {
            // 获取作为当前顶点作为起点的边
            Edge<V, E> edge = outIterator.next();
            // 从边的视角来说作为 出度 即就是终点的入度
            edge.to.inEdges.remove(edge);
            // 迭代器中删除-从集合中删除
            outIterator.remove();
            // 边集合中删除
            edges.remove(edge);
        }

        // 当前节点的作为入度的迭代器
        Iterator<Edge<V, E>> inIterator = vertex.inEdges.iterator();
        while (inIterator.hasNext()) {
            // 获取作为当前顶点作为终点的边
            Edge<V, E> edge = inIterator.next();
            // 从边的视角来说作为 入度 即就是起点的出度
            edge.from.outEdges.remove(edge);
            // 迭代器中删除-从集合中删除
            inIterator.remove();
            // 边集合中删除
            edges.remove(edge);
        }
    }

    @Override
    public void removeEdge(V from, V to) {
        // 判断顶点是否存在
        Vertex<V, E> fromVertex = vertices.get(from);
        if (fromVertex == null) return;

        Vertex<V, E> toVertex = vertices.get(to);
        if (toVertex == null) return;

        // 构建一条基于当前值的边
        Edge<V, E> edge = new Edge<>(fromVertex,toVertex);

        if (fromVertex.outEdges.remove(edge)) {
            fromVertex.inEdges.remove(edge);
            edges.remove(edge);
        }
    }

    @Override
    public void bfs(V v, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        // 根据传入的顶点值 获取顶点
        Vertex<V, E> beginVertex = vertices.get(v);
        if (beginVertex == null) return;

        // 将遍历过的节点存入到 set 中保证只遍历一次
        Set<Vertex<V, E>> set = new HashSet<>();
        set.add(beginVertex);

        Queue<Vertex<V, E>> queue = new LinkedList<>();
        queue.offer(beginVertex);

        while (!queue.isEmpty()){
            Vertex<V, E> vertex = queue.poll();
            if (visitor.visit(vertex.v)) return;
            set.add(vertex);

            for (Edge<V,E> outEdge : vertex.outEdges) {
                if (set.contains(outEdge.to)) continue;
                queue.offer(outEdge.to);
            }
        }
    }

    @Override
    public void dfs(V v, VertexVisitor<V> visitor) {
        if (visitor == null) return;
        Vertex<V, E> beginVertex = vertices.get(v);
        if (beginVertex == null) return;
        dfs(beginVertex, new HashSet<>(), visitor);
    }

    private void dfs(Vertex<V, E> vertex, Set<Vertex<V,E>> set, VertexVisitor<V> visitor){
        if (visitor.visit(vertex.v)) return;
        set.add(vertex);

        for (Edge<V,E> outEdge : vertex.outEdges) {
            if (set.contains(outEdge.to)) continue;
            dfs(outEdge.to, set, visitor);
        }
    }

    @Override
    public void difOfStack(V v, VertexVisitor<V> visitor) {
        Vertex<V, E> beginVertex = vertices.get(v);
        if (beginVertex == null) return;

        Set<Vertex<V, E>> set = new HashSet<>();
        Stack<Vertex<V ,E>> stack = new Stack<>();

        // 访问起点
        stack.push(beginVertex);
        set.add(beginVertex);
        if (visitor.visit(beginVertex.v)) return;

        while (!stack.isEmpty()){
            Vertex<V, E> vertex = stack.pop();
            // 遍历当前节点作为起点的边
            for (Edge<V, E> edge : vertex.outEdges) {
                // 访问过就跳过
                if (set.contains(edge.to)) continue;

                // 起点和终点都入栈
                stack.push(edge.from);
                stack.push(edge.to);

                // 加入到set
                set.add(edge.to);
                if (visitor.visit(edge.to.v)) return;
                break;
            }
        }
    }

    @Override
    public List<V> topologicalSort() {
        List<V> list = new ArrayList<>();
        Queue<Vertex<V, E>> queue = new LinkedList<>();
        HashMap<Vertex<V, E>, Integer> map = new HashMap<>();

        // 将所有的入度为0的顶点加入到队列中
        vertices.forEach((V v, Vertex<V,E> vertex) ->{
            int size = vertex.inEdges.size();
            if (size == 0){
                queue.offer(vertex);
            }else {
                map.put(vertex,size);
            }
        });

        while (!queue.isEmpty()){
            Vertex<V, E> vertex = queue.poll();
            list.add(vertex.v);
            for (Edge<V, E> edge : vertex.outEdges) {
                int size = map.get(edge.to) - 1;
                if (size == 0){ // 入度为 0 加入到队列中
                    queue.offer(edge.to);
                }else { // 不为 0 入度减一
                    map.put(edge.to,size);
                }
            }
        }
        return list;
    }

    @Override
    public Set<EdgeInfo<V, E>> mst() {
        return kruskal();
    }

    @Override
    public Map<V, E> shortestPath(V begin) {
        return dijkstra(begin);
    }

    @Override
    public Map<V, PathInfo<V, E>> shortestPathHaveInfo(V begin) {
        return bellmanFord(begin);
    }

    @Override
    public Map<V, Map<V, PathInfo<V, E>>> shortestPath() {
        Map<V, Map<V, PathInfo<V, E>>> paths = new HashMap<>();

        // 初始化
        for (Edge<V, E> edge : edges) {
            // 获取当前边起点的值
            Map<V, PathInfo<V, E>> map = paths.get(edge.from.v);
            // 如果为空，就新建一个map并且放到要返回的集合中
            if (map == null) {
                map = new HashMap<>();
                paths.put(edge.from.v, map);
            }
            // 将该边的权值 和 起点顶点信息加入到map中
            PathInfo<V, E> pathInfo = new PathInfo<>(edge.weight);
            pathInfo.getEdges().add(edge.info());
            map.put(edge.to.v, pathInfo);
        }

        // 三层循环遍历
        // v2 = k
        // v1 = i
        // v3 = j
        vertices.forEach((V v2, Vertex<V, E> vertex2) -> {
            vertices.forEach((V v1, Vertex<V, E> vertex1) -> {
                vertices.forEach((V v3, Vertex<V, E> vertex3) -> {
                    // 如果其中有顶点相同就退出当前循环，不需要处理
                    if (v1.equals(v2) || v2.equals(v3) || v1.equals(v3)) return;

                    // 分别获取三条最短路径

                    // v1 -> v2
                    PathInfo<V, E> path12 = getPathInfo(v1, v2, paths);
                    if (path12 == null) return;

                    // v2 -> v3
                    PathInfo<V, E> path23 = getPathInfo(v2, v3, paths);
                    if (path23 == null) return;

                    // v1 -> v3
                    PathInfo<V, E> path13 = getPathInfo(v1, v3, paths);

                    // 获取 i -> k + k -> j 权值
                    E newWeight = weightManager.add(path12.getWeight(), path23.getWeight());
                    // 如果是新值大或者是原先的值为空，就不要处理
                    if (path13 != null &&
                            weightManager.compare(newWeight, path13.getWeight()) >= 0) return;

                    if (path13 == null) { // 如果原先的值不存在，就新建一个变量，加入到map中
                        path13 = new PathInfo<V, E>();
                        paths.get(v1).put(v3, path13);
                    } else { // 清空原先存储的路径信息
                        path13.getEdges().clear();
                    }

                    // 重新赋值权值
                    path13.setWeight(newWeight);

                    // 设置心得最短路径：将 i -> k + k -> j 赋值给 i -> j
                    path13.getEdges().addAll(path12.getEdges());
                    path13.getEdges().addAll(path23.getEdges());
                });
            });
        });

        return paths;
    }

    /**
     * 获取当前map中存储的最短路径
     * @param from 起点
     * @param to 终点
     * @param paths map
     * @return
     */
    private PathInfo<V, E> getPathInfo(V from, V to, Map<V, Map<V, PathInfo<V, E>>> paths) {
        Map<V, PathInfo<V, E>> map = paths.get(from);
        return map == null ? null : map.get(to);
    }

    /**
     * 最短路径 bellman-ford ，包含路径信息
     * @param begin
     * @return
     */
    private Map<V,PathInfo<V, E>> bellmanFord(V begin){
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        // 已经确定的最短路径集合 :
            // v - 节点值
            // k- PathInfo<V, E>:
                // k - 最短路径，
                // v - 路径权值；
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();

        // 初始化当前顶点到自己的权值大小。
        PathInfo<V, E> beginPath = new PathInfo<>();
        beginPath.setWeight(weightManager.zero());
        selectedPaths.put(begin,beginPath);

        // 最多执行多少轮松弛
        int count = vertices.size() - 1;
        for (int i = 0; i < count; i++) {
            for (Edge<V, E> edge : edges) {
                // 获取当前路径起点已经存在的路径信息，如果不存在则不能进行松弛。
                PathInfo<V, E> fromPath = selectedPaths.get(edge.from.v);
                if (fromPath == null) continue;
                // 传入当前边，起点路径信息，等待返回信息
                relaxOfBellmanFord(edge, fromPath, selectedPaths);
            }
        }
        // 如果已经完毕 v - 1 轮松弛操作，但依然可以对某些边进行松弛，就表示无法得出最短路径
        // 即存在负权环。
        for (Edge<V, E> edge : edges) {
            PathInfo<V, E> fromPath = selectedPaths.get(edge.from.v);
            if (fromPath == null) continue;
            if (relaxOfBellmanFord(edge, fromPath, selectedPaths)) {
                System.out.println("有负权环");
                return null;
            }
        }
        // 删除到自己的权值和路径相关
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 松弛
     * @param edge 需要进行松弛的边
     * @param fromPath edge的from的最短路径信息
     * @param paths 存放着其他点（对于dijkstra来说，就是还没有离开桌面的点）的最短路径信息
     */
    private boolean relaxOfBellmanFord(Edge<V, E> edge, PathInfo<V, E> fromPath, Map<V, PathInfo<V, E>> paths) {
        // 计算新的权值
        E newWeight = weightManager.add(fromPath.getWeight(), edge.weight);
        // 获取之前的路径信息
        PathInfo<V, E> oldPath = paths.get(edge.to.v);
        // 如果路径不为空，并且新权值大于之前的权值，不需要松弛
        if (oldPath != null
                && weightManager.compare(newWeight, oldPath.getWeight()) >= 0) return false;

        // 保证oldPath不为空
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to.v, oldPath);
        } else { // 清空原有的路径信息
            oldPath.getEdges().clear();
        }

        // 重新添加路径 和 权值
        oldPath.setWeight(newWeight);
        oldPath.getEdges().addAll(fromPath.getEdges());
        oldPath.getEdges().add(edge.info());
        return true;
    }

    /**
     * 最短路径 dijkstra ，包含路径信息
     * @param begin
     * @return
     */
    private Map<V,PathInfo<V, E>> dijkstraHaveInfo(V begin){
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        // 已经确定的最短路径集合 v - 节点值 ；E - 权值
        Map<V, PathInfo<V, E>> selectedPaths = new HashMap<>();
        // 等待确认的集合，存储等待进行松弛的值
        Map<Vertex<V, E>, PathInfo<V, E>> paths = new HashMap<>();
        // 初始化 paths 将begin的出度直接连的顶点加入到其中
        for (Edge<V, E> edge : beginVertex.outEdges) {
            PathInfo<V, E> pathInfo = new PathInfo<>();
            // 将边和权值信息加入到 pathInfo 中
            pathInfo.getEdges().add(edge.info());
            pathInfo.setWeight(edge.weight);
            paths.put(edge.to, pathInfo);
        }
        while (!paths.isEmpty()){
            // 获取可以直接到达且权值最小的的顶点
            Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = getMinPathHaveInfo(paths);
            Vertex<V, E> minVertex = minEntry.getKey();
            PathInfo<V, E> minPath = minEntry.getValue();
            // 加入到确定的路径中
            selectedPaths.put(minVertex.v, minEntry.getValue());
            // 删除等待确认的
            paths.remove(minVertex);
            // 松弛
            for (Edge<V, E> edge : minVertex.outEdges) {
                // 如果已经确定最短路径，不需要再进行松弛
                if (selectedPaths.containsKey(edge.to.v)) continue;
                // 松弛
                relax(edge, minPath, paths);
            }
        }
        // 删除到达起点的路径
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 获取当前最短路径，包含路径信息
     * @param paths
     * @return
     */
    private Map.Entry<Vertex<V, E>, PathInfo<V, E>> getMinPathHaveInfo(Map<Vertex<V, E>, PathInfo<V, E>> paths){
        // 获取迭代器
        Iterator<Map.Entry<Vertex<V, E>, PathInfo<V, E>>> iterator = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, PathInfo<V, E>> minEntry = iterator.next();
        while (iterator.hasNext()){
            Map.Entry<Vertex<V, E>, PathInfo<V, E>>entry = iterator.next();
            if (weightManager.compare(minEntry.getValue().getWeight(), entry.getValue().getWeight()) > 0){
                minEntry = entry;
            }
        }
        return minEntry;
    }

    /**
     * 松弛
     * @param edge 松弛的边
     * @param fromPath 边的起点最短路径信息
     * @param paths 其它待松弛的最短路径的信息
     */
    private void relax(Edge<V, E> edge,PathInfo<V, E> fromPath ,Map<Vertex<V, E>, PathInfo<V, E>> paths){
        E newWeight = weightManager.add(fromPath.getWeight(), edge.weight);
        PathInfo<V, E> oldPath = paths.get(edge.to);
        // 不符合松弛条件，忽略
        if (oldPath != null &&  weightManager.compare(newWeight, oldPath.getWeight()) >=  0) return;
        // 以前不存在该路径
        if (oldPath == null) {
            oldPath = new PathInfo<>();
            paths.put(edge.to, oldPath);
        }else {
            // 清空之前的路径信息
            oldPath.getEdges().clear();
        }
        oldPath.setWeight(newWeight);
        // 将之前已经选中的和当前选中的都加入到pathInfo
        oldPath.getEdges().addAll(fromPath.edges);
        oldPath.getEdges().add(edge.info());
        paths.put(edge.to, oldPath);
    }

    /**
     * 最短路径 dijkstra
     * @param begin
     * @return
     */
    private Map<V, E> dijkstra(V begin){
        Vertex<V, E> beginVertex = vertices.get(begin);
        if (beginVertex == null) return null;
        // 已经确定的最短路径集合 v - 节点值 ；E - 权值
        Map<V, E> selectedPaths = new HashMap<>();
        // 等待确认的集合，存储等待进行松弛的值
        Map<Vertex<V, E>, E> paths = new HashMap<>();
        // 初始化 paths 将begin的出度直接连的顶点加入到其中
        for (Edge<V, E> edge : beginVertex.outEdges) {
            paths.put(edge.to, edge.weight);
        }
        while (!paths.isEmpty()){
            // 获取可以直接到达且权值最小的的顶点
            Map.Entry<Vertex<V, E>, E> minEntry = getMinPath(paths);
            Vertex<V, E> minVertex = minEntry.getKey();
            // 加入到确定的路径中
            selectedPaths.put(minVertex.v, minEntry.getValue());
            // 删除等待确认的
            paths.remove(minVertex);
            // 松弛
            for (Edge<V, E> edge : minVertex.outEdges) {
                // 如果已经确定最短路径，不需要再进行松弛
                if (selectedPaths.containsKey(edge.to.v)) continue;
                E newWeight = weightManager.add(minEntry.getValue(), edge.weight);
                E oldWeight = paths.get(edge.to);
                if (oldWeight == null || weightManager.compare(newWeight, oldWeight) < 0){
                    paths.put(edge.to, newWeight);
                }
            }
        }
        // 删除到达起点的路径
        selectedPaths.remove(begin);
        return selectedPaths;
    }

    /**
     * 获取当前最短路径
     * @param paths
     * @return
     */
    private Map.Entry<Vertex<V, E>, E> getMinPath(Map<Vertex<V, E>, E> paths){
        // 获取迭代器
        Iterator<Map.Entry<Vertex<V, E>, E>> iterator = paths.entrySet().iterator();
        Map.Entry<Vertex<V, E>, E> minEntry = iterator.next();
        while (iterator.hasNext()){
            Map.Entry<Vertex<V, E>, E> entry = iterator.next();
            if (weightManager.compare(minEntry.getValue(),entry.getValue()) > 0){
                minEntry = entry;
            }
        }
        return minEntry;
    }

    /**
     * prim 最小生成树
     * @return
     */
    private Set<EdgeInfo<V, E>> prim(){
        // 获取顶点迭代器 如果迭代器为空则返回null
        Iterator<Vertex<V, E>> iterator = vertices.values().iterator();
        if (!iterator.hasNext()) return null;
        // 返回边集
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        // 已经加入到最小生成树中的顶点集
        Set<Vertex<V,E>> added = new HashSet<>();
        Vertex<V, E> vertex = iterator.next();
        added.add(vertex);
        // 初始化构建小顶堆，传入第一个顶点的出度边集合 和 比较器
        MinHeap<Edge<V, E>> heap = new MinHeap<>(vertex.outEdges,edgeComparator);
        int size = vertices.size();
        // 当堆中有元素 并且 已经处理的顶点数量小于总数量时才需要进行处理
        while (!heap.isEmpty() && edgeInfos.size() < size){
            // 权值最小的边，一定是最小生成树的一部分
            Edge<V, E> edge = heap.remove();
            // 如果当前点已经被加入到该集合中 表示已经对其处理完毕 不需要再加入到堆中进行处理
            if (added.contains(edge.to)) continue;
            // 把组成最小生成树的边放入到返回的集合中
            edgeInfos.add(edge.info());
            added.add(edge.to);
            // 将该边终点的所有出度边加入到堆中
            heap.addAll(edge.to.outEdges);
        }
        return edgeInfos;
    }

    /**
     * kruskal 最小生成树
     * @return
     */
    private Set<EdgeInfo<V, E>> kruskal(){
        int size = vertices.size() - 1;
        if (size <= 1) return null;
        // 最小生成树 边 集合
        Set<EdgeInfo<V, E>> edgeInfos = new HashSet<>();
        // 将所有的边都加入到小顶堆中
        MinHeap<Edge<V, E>> heap = new MinHeap<>(edges,edgeComparator);
        // 初始化并查集，将每个顶点都作为一个集合
        UnionFind<Vertex<V, E>> unionFind = new UnionFind<>();
        vertices.forEach((V v , Vertex<V, E> vertex) ->{
            unionFind.makeSet(vertex);
        });
        while (!heap.isEmpty() && edgeInfos.size() < size){
            // 获得权值最小的边
            Edge<V, E> edge = heap.remove();
            // 判断是否成环 ，成环就抛弃 当前边
            if (unionFind.isSame(edge.from, edge.to)) continue;
            // 将最小的边加入到最小生成树中
            edgeInfos.add(edge.info());
            // 将当前边的两个顶点加入到并查集中
            unionFind.union(edge.from, edge.to);
        }
        return edgeInfos;
    }

    /**
     * 顶点类
     * @param <V>
     * @param <E>
     */
    private static class Vertex<V,E>{
        // 顶点值
        V v;
        // 以该顶点为终点的边 入度
        Set<Edge<V, E>> inEdges = new HashSet<>();
        // 以该顶点为起点的边 出度
        Set<Edge<V, E>> outEdges = new HashSet<>();

        public Vertex(V v) {
            this.v = v;
        }

        @Override
        public boolean equals(Object o) {
            // 顶点值相等就表示顶点相等
            return Objects.equals(v, ((Vertex<V,E>) o).v) ;
        }

        @Override
        public int hashCode() {
            return Objects.hash(v);
        }

        @Override
        public String toString() {
            return v == null ? "null" : v.toString();
        }
    }

    /**
     * 边类
     * @param <V>
     * @param <E>
     */
    private static class Edge<V,E>{
        // 起点顶点
        Vertex<V, E> from;
        // 终点顶点
        Vertex<V, E> to;
        // 权值
        E weight;

        Edge(Vertex<V, E> from, Vertex<V, E> to) {
            this.from = from;
            this.to = to;
        }

        Edge(Vertex<V, E> from, Vertex<V, E> to, E weight) {
            this.from = from;
            this.to = to;
            this.weight = weight;
        }

        EdgeInfo<V, E> info(){
            return new EdgeInfo<V, E>(from.v, to.v, weight);
        }

        @Override
        public boolean equals(Object o) {
            // 起点终点相同就是同一条边
            return Objects.equals(from, ((Edge<V,E>) o).from) &&  Objects.equals(to, ((Edge<V,E>) o).to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(from, to);
        }

        @Override
        public String toString() {
            return "Edge{" +
                    "from=" + from +
                    ", to=" + to +
                    ", weight=" + weight +
                    '}';
        }
    }

}
